מבני נתונים אלמנטריים:

• מידע שמור בזיכרון. תא זיכרון מכיל ערך בודד, אליו אפשר להיכנס בזמן קבוע.

• ניתן להשתמש במספר תאים ברצף.

• ניתן גם לקשר בין תאים באמצעות מצביעים.

• המבנים האלמנטרים הבסיסיים:

  • מערך:
    • בנוי מתאי זיכרון רציפים
    • תומך בפעולות הבאות:
      • בניית מערך בגודל קבוע (סיבוכיות $\mathrm{\Theta }(1)$).
      • גישה לאלמנט (סיבוכיות $\mathrm{\Theta }(1)$).
  • רשימה מקושרת:
    • בנוי מתאי זיכרון מפוזרים, אשר מקושרים ביניהם באמצעות מצביעים
    • תומכת בפעולות הבאות:
      • יצירת רשימה ריקה.
      • גישה לאלמנטים לפי סדר הרשימה.
      • הכנסה של אלמנט חדש.
      • מחיקה של אלמנט.
    • ברשימה מקושרת רגילה לכל אלמנט יש מצביע לאלמנט הבא
    • ברשימה מקושרת דו כיוונית לכל אלמנט יש מצביע לאלמנט הבא והקודם.

• סנטינל:

  • חוליה שנוצרת עם המבנה ולא מכילה נתונים.
  • ברשימה מקושרת הסנטינל היא הראש (L.head) אשר מצביע על האיבר הראשון (באמצעות L.next) (שמצביע עליה בחזרה ברשימה דו כיוונית). האיבר האחרון מצביע עליו (באמצעות L.next) (והוא מצביע עליו בחזרה ברשימה דו כיוונית באמצעות L.prev).
  • 

• מבנה עץ:

  • מבנה המתאר היררכיה בין איברים במבנה
  • האיברים בעץ נקראים קודקודים (nodes). כאשר יש קודקודים מיוחדים:
    • שורש: האב הקדמון של כל מי שמתחתיו.
    • עלים: קודקודים בלי ילדים.
    • אב ובן: אב הוא מי שנמצא מעל בנו, בן הוא מי שנמצא מתחת לאב.
    • קודקוד פנימי: קודקוד שהוא לא עלה.
  • תת עץ:
    • הקודקוד שמתחיל את תת העץ הופך לשורש וכל הצאצאים שלו הופכים לקודקודים.
  • עומק:
    • מספר הצעדים שצריך לעשות מקודקוד עד שמגיעים לשורש.
    • עומק של שורש הוא 0.
  • גובה:
    • מספר הצעדים שצריך לעשות מקודקוד לעלה הכי נמוך.
    • גובה של עלה הוא 0.
  • דרגה:
    • מספר הבנים של אותו קודקוד.
    • קודקוד ללא בנים הוא בעל דרגה 0.
    • מכאן ניתן להגדיר שעלה הוא בעל דרגה 0.
  • עץ בינארי:
    • עץ שבו הדרגה של כל קודקוד היא 2 לכל היותר.
    • לשני הבנים האלו נקרא בן שמאלי ובן ימני.
    • עץ בינארי מלא: לכל קודקוד פנימי יש בדיוק 2 ילדים
    • עץ בינארי מושלם: הוא גם מלא וגם כל העלים בדיוק באותה רמה.
    • עץ בינארי שלם: אם הוא עץ מושלם, או שהוא עץ שהיה מושלם והתחילו למחוק עלים מימין לשמאל.
    • עץ חיפוש בינארי:

      • כל קודקוד בצד ימין גדול מאביו, וכל קודקוד בצד שמאל קטן מאביו.

      • כל המפתחות בבן השמאלי קטנים מהשורש, וכל המפתחות בבן הימני גדולים מהשורש.

      • קודקוד מכיל את השדות הבאים:

        • המפתח לפיו הוא מקבל מיקום בעץ.
        • מידע נוסף (אופציונלי).
        • מצביע לבן השמאלי והימני (יכולים להיות NULL).
        • מצביע לאב (אופציונלי ו - NULL עבור השורש).

      • סוגי הסריקות על העץ:

        • סריקת inorder:
          • קודם מה שבשמאל, ואז הקודקוד, ואז הימנים.
          • מתחילים מהעלה הקטן ביותר.
          • התוצאה החוזרת היא ממויינת.
          • סיבוכיות הזמן היא $\mathrm{\Theta }(n)$
        • סריקת preorder:
          • קודם הקודקוד ואז הבן השמאלי ואז הבן הימני.
        • סריקת postorder:
          • קודם בן שמאלי, ואז ימני, ואז קודקוד.
        • לדוגמא:

      • חיפוש בעץ:

        • חיפוש רקורסיבי: סיבוכיות $\mathrm{\Theta }(h)$ כאשר h הוא גובה העץ.
        • חיפוש איטרטיבי: סיבוכיות $\mathrm{\Theta }(h)$ כאשר h הוא גובה העץ.

      • הוספה לעץ:

        • נכנס כעלה, בסיבוכיות $\mathrm{\Theta }(h)$ ותוך שמירה על חוקי העץ הבינארי.

      • מחיקה מעץ:

        • במחיקה מעץ ישנן שלוש אופציות:
        1. הקודקוד הוא עלה:
           • פשוט נמחוק את הקודקוד, ללא הזזות.
        2. לקודקוד יש בן אחד:
           • נמחוק את הקודקוד, ונהפוך את הבן להיות הבן של אב הקודקוד.
        3. לקודקוד יש שני בנים:
           • נמצא מי היורש של הקודקוד (היורש גדול יותר מהקודקוד וכל הערכים שאותו קודקוד גדול מהם, אך קטן מכל השאר).
           • נמחוק את היורש ממקומו ונשים אותו במקום הקודקוד שנרצה למחוק.

מבני נתונים אבסטרקטיים:

• מגדיר נתונים שצריך לשמור ופעולות מסוימות שצריכות לקרות.

• מימוש המבנה לא משנה (מכיון שיש דרכים שונות לממש את אותו הקונספט).

• מבנה מחסנית:

  • אוסף של איברים שמסוגל לבצע את הפעולות הבאות:
    • פעולת create: יצירת מבנה מחסנית ריקה.
    • פעולת isEmpty(S): מחזיר בוליאני לפי אם המחסנית S ריקה.
    • פעולת push(S, x): הוספת איבר x למחסנית S.
    • פעולת pop(S): קבלת האיבר האחרון שהוכנס והוצאתו מהמחסנית.
  • הסיבוכיות עבור מחסנית אשר ממומשת באמצעות רשימה מקושרת:
    • סיבוכיות מקום $\mathrm{\Theta }(n)$
    • פעולות אלמנטריות (create, isEmpty, pop, push): $\mathrm{\Theta }1$

• מבנה תור:

  • אוסף של איברים שמסוגל לבצע את הפעולות הבאות:
    • פעולת create: יצירת מבנה תור ריק.
    • פעולת isEmpty(Q): מחזיר בוליאני לפי אם התור S ריק.
    • פעולת enqueue(Q, x): הוספת איבר x לתור S.
    • פעולת dequeue(Q): קבלת האיבר הראשון שהוכנס והוצאתו מהתור.